package com.exam.practice;

import java.util.Arrays;
import java.util.List;

/**
 * @Author: xin.wang  E-mail:xin.wang1@myt11.com
 * @CreateTime: 2022/1/12 14:29
 * @Description: 反转链表
 */
public class FirstPractice {
    /**
     * 描述:给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。
     * 要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
     * 如,当输入链表{1,2,3}时，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
     *
     * 用两种解法:
     * 01.采用循环的方式来做
     * 02.采用递归的方式来做
     * @param args
     */
    public static void main(String[] args) {
        FirstPractice firstPractice =new FirstPractice();
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
        ListNode listNode = firstPractice.createList(list);
        ListNode reverseList = firstPractice.reverseList(listNode);
        firstPractice.printList(reverseList);
        System.out.println("------------------");
        ListNode listNode1 = firstPractice.createList(list);
        ListNode reverseList2 = firstPractice.reverseList2(listNode1);
        firstPractice.printList(reverseList2);
    }

    /**
     * 01.循环
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head){
        //定义节点,头节点指向null
        ListNode pHead = null;
        ListNode cur = head;
        //用来保存下一个节点
        ListNode t = null;
        while (cur!=null) {
            //当前结点的下一个节点
            t = cur.next;
            //当前节点给头节点
            cur.next = pHead;
            //前进一位
            pHead = cur;
            cur = t;
        }
        return pHead;
    }

    /**
     * 02.递归
     * @param pHead
     * @return
     */
    public ListNode reverseList2(ListNode pHead){
        //如果当前节点为空或者下一个节点为空
        if (pHead==null || pHead.next==null){
            return pHead;
        }
        //此时cur为最后节点
        ListNode cur = reverseList2(pHead.next);
        //pHead=4, pHead.next=5, pHead.next.next=null
        // 4.next.next=4, 5.next=4
        pHead.next.next = pHead;
        //断开指向箭头, 4.next=null
        pHead.next = null;
        //每层递归都返回cur
        return cur;
    }

    /**
     * 将list里的值转换成ListNode节点
     * @param list
     * @return
     */
    public ListNode createList(List<Integer> list) {
        if (list.isEmpty()){
            return null;
        }
        ListNode headNode = new ListNode(list.get(0));
        ListNode tempNode = createList(list.subList(1, list.size()));
        headNode.setNext(tempNode);
        return headNode;
    }

    /**
     * 打印
     * @param node
     */
    public void printList(ListNode node){
        while (node != null){
            System.out.print(node.getValue());
            System.out.print(" ");
            node = node.getNext();
        }
        System.out.println();
    }


    private static class ListNode {
        private final int value;
        private ListNode next;

        public ListNode(int value) {
            this.value = value;
            this.next = null;
        }

        public int getValue() {
            return value;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }
    }

}

